#define _CRT_SECURE_NO_WARNINGS 1

/*
给定数列1,1,1,3,5,9,17,⋯从第 4 项开始，每项都是前 3 项的和

求第 20190324 项的最后 4 位数字
*/


#include <stdio.h>
#include <stdlib.h>

int main(int argc, char* argv[])
{
    int a = 1, b = 1, c = 1;
    int n = 20190324;
    int i, d;

    for (i = 3; i < n; i++)
    {
        d = (a + b + c) % 10000;// (a+b)%p=(a%p+b%p)%p

        a = b; b = c; c = d;
    }

    printf("%04d", d);

    system("pause");
    return 0;
}